/* 模块：distinct
 * 类型：函数单体
 * 功能：去除一个序列重复的元素
 * 用法：
 * TODO ===========================================================
 * 
 * 注意：
 * - 要求该序列的元素可以两两比较
 */

#ifndef xpack_algo_distinct
#define xpack_algo_distinct
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::algo_distinct::inc
#include"docker/hashmap.hpp"
#include"interface/can_alloc_seq.hpp"
#include"interface/unified_seq.hpp"
#include"macro/xexport.hpp"
#include"macro/xunlikely.hpp"
#include"meta/item_origin_of.hpp"
#pragma pop_macro("xuser")

namespace mixc::algo_distinct{
    /**
     * @brief 
     * 去除重复元素并保证顺序不改变
     * @tparam seq_t 满足 can_unified_seqlize 约束的序列类型
     * @tparam alloc_t 满足 can_alloc_seq 约束的序列分配器回调
     * @param seq 原始序列
     * @param alloc 分配器
     * @return auto 从分配器返回的序列缓冲区
     */
    template<
        inc::can_unified_seqlize        seq_t,
        inc::can_alloc_seq              alloc_t
    >
    inline auto distinct_core(seq_t const & seq, alloc_t const & alloc){
        using namespace inc;
        using item_t                = inc::item_origin_of<seq_t>;

        if (seq->length == zero){
            return alloc(length{0});
        }

        hashmap<item_t, uxx> map{
            length{seq->length}
        };

        for(uxx i = 0, ii = 0; i < seq->length; i++){
            // 注意：
            // hashmap_set_result_t    r;
            // auto key = xmodify(range[i]); // 错误0：获取指针导致 key 在 map 中始终是唯一的，实际上需要获取值
            // map.set(key, ii, xmodify(r)); // 错误1：覆盖 key 对应的 ii，导致索引被覆盖
            // 
            // // 如果之前不存在
            // if (r != hashmap_set_result_t::override){
            //     ii += 1;
            // }

            // 如果之前不存在
            if (auto & key = seq[i]; not map.is_contains(key)){
                map.set(key, ii);
                ii += 1;
            }
        }

        auto buffer = alloc(
            length{map->length}
        );

        // 缓冲区申请失败
        xunlikely(buffer->length == zero){
            return buffer;
        }

        map.foreach([&](item_t const & key, uxx const & val){
            buffer[val] = key;
        });
        return buffer;
    }
}

namespace mixc::algo_distinct::origin{
    /**
     * @brief 
     * 去除重复元素并保证顺序不改变
     * @tparam seq_t 满足 can_unified_seqlize 约束的序列类型
     * @tparam alloc_t 满足 can_alloc_seq 约束的序列分配器回调
     * @param seq 原始序列
     * @param alloc 分配器
     * @return auto 从分配器返回的序列缓冲区
     */
    template<
        inc::can_unified_seqlize        seq_t,
        inc::can_alloc_seq              alloc_t
    >
    inline auto distinct(seq_t const & seq, alloc_t const & alloc){
        auto seqx                   = inc::unified_seq<seq_t>(seq);
        auto allocx                 = inc::can_alloc_seq_helper(alloc);
        return distinct_core(seqx, allocx);
    }
}

#endif

xexport_space(mixc::algo_distinct::origin)
